Search for: All records

This article presents I/O-efficient algorithms for topologically sorting a directed acyclic graph and for the more general problem identifying and topologically sorting the strongly connected components of a directed graph G = ( V, E ). Both algorithms are randomized and have I/O-costs O ( sort ( E ) · poly(log V)), with high probability, where sort ( E ) = O( E / B log M / B ( E/B )) is the I/O cost of sorting an | E |-element array on a machine with size- B blocks and size- M cache/internal memory. These are the first algorithms for these problems that do not incur at least one I/O per vertex, and as such these are the first I/O-efficient algorithms for sparse graphs. By applying the technique of time-forward processing, these algorithms also imply I/O-efficient algorithms for most problems on directed acyclic graphs, such as shortest paths, as well as the single-source reachability problem on arbitrary directed graphs. 

Abstract We have developed an optical method for accurate concentration,er, anddranalysis of amino alcohols based on a simple mix‐and‐measure workflow that is fully adaptable to multiwell plate technology and microscale analysis. The conversion of the four aminoindanol stereoisomers with salicylaldehyde to the corresponding Schiff base allows analysis of thedrbased on a change in the UV maximum at 420 nm that is very different for the homo‐ and heterochiral diastereomers and of the concentration of the sample using a hypsochromic shift of another absorption band around 340 nm that is independent of the analyte stereochemistry. Subsequent in situ formation of Cu^IIassemblies in the absence and presence of base enables quantification of theervalues for each diastereomeric pair by CD analysis. Applying a linear programming method and a parameter sweep algorithm, we determined the concentration and relative amounts of each of the four stereoisomers in 20 samples of vastly different stereoisomeric compositions with an averaged absolute percent error of 1.7 %.